﻿
///四种情况的买股票问题的最佳时机：


//1.含有冷冻期：
//给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
//
//设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票） :
//
//卖出股票后，你无法在第二天买入股票(即冷冻期为 1 天)。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//
//
//
//示例 1:
//
//输入: prices = [1, 2, 3, 0, 2]
//输出 : 3
//解释 : 对应的交易状态为 : [买入, 卖出, 冷冻期, 买入, 卖出]
//示例 2 :
//
//    输入 : prices = [1]
//    输出 : 0


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //都是表示当天操作完后的状态：
          //dp[i][0]:买入状态
          //dp[i][1]:卖出状态
          //dp[i][2]:冷冻期状态
        vector<vector<int>>dp(prices.size() + 1, vector<int>(3));
        dp[0][0] = -prices[0];
        for (int i = 1; i <= prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][2] - prices[i - 1], dp[i - 1][0]);//（可以是之前买入，然后处于保持，也可以是当天买入）
            dp[i][1] = max(dp[i - 1][0] + prices[i - 1], max(dp[i - 1][2], dp[i - 1][1]));//（可以是之前卖出，但是不是前一天，也可以是当天卖出,或者冷冻期）
            dp[i][2] = dp[i - 1][1];//冷冻期前一天必定是卖出（非保持）
        }
        return max(dp[prices.size()][1], dp[prices.size()][2]);

    }
};


//2.含有手续费：
//
//给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
//
//你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
//
//返回获得利润的最大值。
//
//注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
//
//
//
//示例 1：
//
//输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
//输出：8
//解释：能够达到的最大利润 :
//在此处买入 prices[0] = 1
//在此处卖出 prices[3] = 8
//在此处买入 prices[4] = 4
//在此处卖出 prices[5] = 9
//总利润 : ((8 - 1) - 2) + ((9 - 4) - 2) = 8
//示例 2：
//
//输入：prices = [1, 3, 7, 5, 10, 3], fee = 3
//输出：6

class Solution {
public:
    //解法一：二维dp(列比较少，直接遍历行就能初始化)：
     // int maxProfit(vector<int>& prices, int fee) {
     //     int n=prices.size();
     //     //dp[i][0]:当前天结束时处于买入状态（当天买入或者保持有票）
     //     //dp[i][1]:当前天结束时处于售出状态(即当天卖掉或者保持无票)
     //     vector<vector<int>>dp(n+1,vector<int>(2));
     //      dp[0][0]=-prices[0];
     //     for(int i=1;i<=n;i++){
     //         dp[i][0]=max(dp[i-1][1]-prices[i-1],dp[i-1][0]);要么当天买入，要么之前就买入了一直处于保持状态
     //         dp[i][1]=max(dp[i-1][0]-fee+prices[i-1],dp[i-1][1]);//要么当天卖出了（注意手续费），要么之前天就卖出了，一直处于保持无股票状态
     //     }
     //     return dp[n][1];
     // }
     //解法二：两个一维dp:
          //f[i]:当前天结束时处于买入状态（当天买入或者保持有票）
          //g[i]:当前天结束时处于售出状态(即当天卖掉或者保持无票)
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int>f(n + 1);
        auto g = f;
        f[0] = -prices[0];
        for (int i = 1; i <= n; i++) {
            f[i] = max(g[i - 1] - prices[i - 1], f[i - 1]);
            g[i] = max(f[i - 1] - fee + prices[i - 1], g[i - 1]);
        }
        return g[n];
    }
};


//3.有最多两次交易次数限制：
//
//给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
//
//设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
//
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//
//
//
//示例 1:
//
//输入：prices = [3, 3, 5, 0, 0, 3, 1, 4]
//输出：6
//解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3 - 0 = 3 。
//随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4 - 1 = 3 。
//示例 2：
//
//输入：prices = [1, 2, 3, 4, 5]
//输出：4
//解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
//注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
//因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
//示例 3：
//
//输入：prices = [7, 6, 4, 3, 1]
//输出：0
//解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
//示例 4：
//
//输入：prices = [1]
//输出：0

class Solution {
public:   //j<=2
    //f[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中有股票的最大钱
    //g[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中无股票的最大钱
   //两个二维状态表示：
  // int maxProfit(vector<int>& prices) {
  //     int n=prices.size();
  //     vector<vector<int>>f(n+1,vector<int>(3,-0x3f3f3f3f));//把无用项初始化算法中的可认为最小值（因为如果是INT_MIN，INT_MAX这样可能会超限；这里
  //     //对0x3f3f3f3f这样使它的一般加一般数不会越界）
  //     auto g=f;
  //     f[0][0]=-prices[0];//为了初始化f[1][0];
  //     g[0][0]=0;//为了初始化g[1][0]
  //     for(int i=1;i<=n;i++){
  //         for(int j=0;j<=2;j++){
  //             f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i-1]);可能上一天也是有股票并未买入，也可能是i这天买入（即i-1这天无股票）
  //             //这里我们不能从1开始遍历j；因为后面否则每个[0][j]我们都要初始化麻烦（因为我们只有第一个00有用，其他都是无关项），
  //             //这里根据防止空访问只需做个判断即可
  //             g[i][j]=j>=1?max(g[i-1][j],f[i-1][j-1]+prices[i-1]):g[i-1][j];要么前一天也是没股票状态，要么当天就把股票卖了
  //         }
  //     }
  //     int ret=0;
  //     for(auto a:g[n]) ret=max(ret,a);//这里由于最后一定是卖掉了也就是g；遍历0-j次交易的最大值即可
  //     return ret;
  // }

    //定义两个三维dp状态（实际遍历填表还是按照二维o(N^2）因为这里两个dp同时填直接第三维是常数级别)：
     //dp[i][j][0]:表示到了i天此次操作结束后是进行了j次交易且手中有股票的最大钱
      //dp[i][j][1]:表示到了i天此次操作结束后是进行了j次交易且手中无股票的最大钱
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<vector<int>>>dp(n + 1, vector<vector<int>>(3, vector<int>(2, -0x3f3f3f3f)));
        dp[0][0][0] = -prices[0];
        dp[0][0][1] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 2; j++) {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] - prices[i - 1]);
                dp[i][j][1] = j >= 1 ? max(dp[i - 1][j][1], dp[i - 1][j - 1][0] + prices[i - 1]) : dp[i - 1][j][1];
            }
        }
        int ret = 0;
        for (int k = 0; k <= 2; k++)ret = max(ret, dp[n][k][1]);
        return ret;

    }
};

//
//4. 最多k次交易次数限制：
//
//给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
//设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//示例 1：
//输入：k = 2, prices = [2, 4, 1]
//输出：2
//解释：在第 1 天(股票价格 = 2) 的时候买入，在第 2 天(股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4 - 2 = 2 。
//示例 2：
//输入：k = 2, prices = [3, 2, 6, 5, 0, 3]
//输出：7
//解释：在第 2 天(股票价格 = 2) 的时候买入，在第 3 天(股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6 - 2 = 4 。
//随后，在第 5 天(股票价格 = 0) 的时候买入，在第 6 天(股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3 - 0 = 3 。


class Solution {
public:
    //j<=2
      //f[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中有股票的最大钱
      //g[i][j]:表示到了i天此次操作结束后是进行了j次交易且手中无股票的最大钱

    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>>f(n + 1, vector<int>(k + 1, -0x3f3f3f3f));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i - 1]);
                g[i][j] = j >= 1 ? max(g[i - 1][j], f[i - 1][j - 1] + prices[i - 1]) : g[i - 1][j];
            }
        }
        int ret = 0;
        for (auto a : g[n]) ret = max(ret, a);
        return ret;
    }
};
